package class02

import (
	"traning/algorithm/utility"
)

func ComeGoMaxPathSum(matrix [][]int) int {
	// 两个小人都从 0，0 出发走向 右下角落
	return ComeGoMaxPathSumProcess(matrix, 0, 0, 0)
}

// (Ar, Ac) 小人A的位置
// (Br, Bc) 小人B的位置 【根据小人走的步数是一样的，可以推出 Bc = Ac + Ar - Br
func ComeGoMaxPathSumProcess(matrix [][]int, Ar, Ac, Br int) int {
	N := len(matrix)-1
	M := len(matrix[0])-1
	if Ar == N && Ac == M {
		// 小人A走到最后一个位置的时候，小人B也走到最后一个位置，只返回该数一次即可
		return matrix[Ar][Ac]
	}

	// 讨论可能性
	// A右 B下
	// A右 B右
	// A下 B下
	// A下 B右
	Bc := Ar + Ac - Br
	ARightBDown := -1
	if Ac < M && Br < N {
		ARightBDown = ComeGoMaxPathSumProcess(matrix, Ar, Ac+1, Br+1)
	}
	ARightBRight := -1
	if  Ac < M && Bc < M {
		ARightBRight = ComeGoMaxPathSumProcess(matrix, Ar, Ac+1, Br)
	}
	ADownBDown := -1
	if Ar < N && Br < N {
		ADownBDown = ComeGoMaxPathSumProcess(matrix, Ar+1, Ac, Br+1)
	}
	ADownBRight := -1
	if Ar < N && Bc < M {
		ADownBRight = ComeGoMaxPathSumProcess(matrix, Ar+1, Ac, Br)
	}
	maxNext := utility.Max(utility.Max(ARightBDown, ARightBRight), utility.Max(ADownBDown, ADownBRight))
	// 小人A与小人B位置相同，返回一个值
	if Ac == Bc {
		return matrix[Ar][Ac] + maxNext
	}
	//  小人A与小人B位置不相同，返回两个值
	return matrix[Ar][Ac] + matrix[Br][Bc] + maxNext
}
